SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Coin problem</title>

</head>

Coin problem

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Not to be confused with <a href="Change-making_problem" title="Change-making problem">Change-making problem</a> or <a href="Coin_rotation_paradox" title="Coin rotation paradox">Coin rotation paradox</a>.</div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .tmulti .multiimageinner{display:flex;flex-direction:column}.mw-parser-output .tmulti .trow{display:flex;flex-direction:row;clear:left;flex-wrap:wrap;width:100%;box-sizing:border-box}.mw-parser-output .tmulti .tsingle{margin:1px;float:left}.mw-parser-output .tmulti .theader{clear:both;font-weight:bold;text-align:center;align-self:center;background-color:transparent;width:100%}.mw-parser-output .tmulti .thumbcaption{background-color:transparent}.mw-parser-output .tmulti .text-align-left{text-align:left}.mw-parser-output .tmulti .text-align-right{text-align:right}.mw-parser-output .tmulti .text-align-center{text-align:center}@media all and (max-width:720px){.mw-parser-output .tmulti .thumbinner{width:100%!important;box-sizing:border-box;max-width:none!important;align-items:center}.mw-parser-output .tmulti .trow{justify-content:center}.mw-parser-output .tmulti .tsingle{float:none!important;max-width:100%!important;box-sizing:border-box;text-align:center}.mw-parser-output .tmulti .tsingle .thumbcaption{text-align:left}.mw-parser-output .tmulti .trow>.thumbcaption{text-align:center}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .tmulti .multiimageinner span:not(.skin-invert-image):not(.skin-invert):not(.bg-transparent) img{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .tmulti .multiimageinner span:not(.skin-invert-image):not(.skin-invert):not(.bg-transparent) img{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="thumb tmulti tright"><div class="thumbinner multiimageinner" style="width:248px;max-width:248px"><div class="trow"><div class="tsingle" style="width:122px;max-width:122px"><div class="thumbimage"></div></div><div class="tsingle" style="width:122px;max-width:122px"><div class="thumbimage"></div></div></div><div class="trow" style="display:flex"><div class="thumbcaption">With only 2 pence and 5 pence coins, one cannot make 3 pence, but one can make any higher integer amount.</div></div></div></div>

In <a href="Mathematics" title="Mathematics">mathematics</a>, the <a href="Coin" title="Coin">coin</a> problem (also referred to as the Frobenius coin problem or Frobenius problem, after the <a href="Mathematician" title="Mathematician">mathematician</a> <a href="Ferdinand_Georg_Frobenius" title="Ferdinand Georg Frobenius">Ferdinand Frobenius</a>) is a <a href="Mathematical_problem" title="Mathematical problem">mathematical problem</a> that asks for the largest <a href="Monetary" class="mw-redirect" title="Monetary">monetary</a> amount that cannot be obtained using only coins of specified <a href="Denomination_(currency)" title="Denomination (currency)">denominations</a>.<a href="#cite_note-ramirez-1">[1]</a> For example, the largest amount that cannot be obtained using only coins of 3 and 5 units is 7 units. The solution to this problem for a given set of coin denominations is called the Frobenius number of the set. The Frobenius number exists as long as the set of coin denominations is <a href="Coprime_integers#Coprimality_in_sets" title="Coprime integers">setwise coprime</a>.

There is an explicit formula for the Frobenius number when there are only two different coin denominations, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">, where the greatest common divisor of these two numbers is 1: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle xy-x-y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle xy-x-y}</annotation>

</semantics>

</math><img src="./dd8c61b2899e04258f6187ab6410a18078d1cbfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.651ex; height:2.343ex;" alt="{\displaystyle xy-x-y}" loading="lazy">. If the number of coin denominations is three or more, no explicit formula is known. However, for any fixed number of coin denominations, there is an <a href="Algorithm" title="Algorithm">algorithm</a> for computing the Frobenius <a href="Number" title="Number">number</a> in <a href="Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</a> (in the logarithms of the coin denominations forming an input).<a href="#cite_note-kannan-2">[2]</a> No known algorithm is polynomial time in the number of coin denominations, and the general problem, where the number of coin denominations may be as large as desired, is <a href="NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a>.<a href="#cite_note-beidhoffer-3">[3]</a><a href="#cite_note-mw-4">[4]</a>

<div class="mw-heading mw-heading2"><h2 id="Statement">Statement</h2></div>

In mathematical terms, the problem can be stated:

<dl><dd>Given positive <a href="Integer" title="Integer">integers</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{1},a_{2},\dots ,a_{n}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{1},a_{2},\dots ,a_{n}}</annotation>

</semantics>

</math><img src="./ccc2b55ae65455992fe3ab08c90c55a0cc2e7709.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.229ex; height:2.009ex;" alt="{\displaystyle a_{1},a_{2},\dots ,a_{n}}" loading="lazy">such that <a href="Greatest_common_divisor" title="Greatest common divisor">gcd</a><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (a_{1},a_{2},\dots ,a_{n})=1}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (a_{1},a_{2},\dots ,a_{n})=1}</annotation>

</semantics>

</math><img src="./9a2cb26709c91f7388329f5ff7b2a3cd0f83b93b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.299ex; height:2.843ex;" alt="{\displaystyle (a_{1},a_{2},\dots ,a_{n})=1}" loading="lazy">, find the largest integer that cannot be expressed as an integer <a href="Conical_combination" title="Conical combination">conical combination</a> of these numbers, i.e., as a sum: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{1}a_{1}+k_{2}a_{2}+\dots +k_{n}a_{n}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k_{1}a_{1}+k_{2}a_{2}+\dots +k_{n}a_{n}}</annotation>

</semantics>

</math><img src="./01c3778118e9bc6b40d916958145462b5f243f93.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:25.221ex; height:2.509ex;" alt="{\displaystyle k_{1}a_{1}+k_{2}a_{2}+\dots +k_{n}a_{n}}" loading="lazy"></dd>

<dd>where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{1},k_{2},\dots ,k_{n}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k_{1},k_{2},\dots ,k_{n}}</annotation>

</semantics>

</math><img src="./da3b789a72bd29255e997281d2af1c57ba0ec4b6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.173ex; height:2.509ex;" alt="{\displaystyle k_{1},k_{2},\dots ,k_{n}}" loading="lazy"> are non-negative integers.</dd></dl>

This largest integer is called the Frobenius number of the set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{a_{1},a_{2},\dots ,a_{n}\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{a_{1},a_{2},\dots ,a_{n}\}}</annotation>

</semantics>

</math><img src="./0ce075b494b4413331976b35aaa6632c98e8f36e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.553ex; height:2.843ex;" alt="{\displaystyle \{a_{1},a_{2},\dots ,a_{n}\}}" loading="lazy">, and is usually denoted by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(a_{1},a_{2},\dots ,a_{n})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(a_{1},a_{2},\dots ,a_{n})}</annotation>

</semantics>

</math><img src="./01f05261ecd07bfd690579b7e321efb87038ba01.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.154ex; height:2.843ex;" alt="{\displaystyle g(a_{1},a_{2},\dots ,a_{n})}" loading="lazy">

The existence of the Frobenius number depends on the condition that the greatest common divisor (GCD) is equal to 1. Indeed, the potential sums are multiples of the GCD in all cases. Hence, if it is not 1, then there are always arbitrarily large numbers that cannot be obtained as sums. For example, if you had two types of coins valued at 6 cents and 14 cents, the GCD would equal 2, and there would be no way to combine any number of such coins to produce a sum which was an <a href="Parity_(mathematics)" title="Parity (mathematics)">odd number</a>; additionally, <a href="Parity_(mathematics)" title="Parity (mathematics)">even numbers</a> 2, 4, 8, 10, 16 and 22 (less than m=24) could not be formed, either. On the other hand, whenever the GCD equals 1, the set of integers that cannot be expressed as a conical combination of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{a_{1},a_{2},\dots ,a_{n}\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{a_{1},a_{2},\dots ,a_{n}\}}</annotation>

</semantics>

</math><img src="./0ce075b494b4413331976b35aaa6632c98e8f36e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.553ex; height:2.843ex;" alt="{\displaystyle \{a_{1},a_{2},\dots ,a_{n}\}}" loading="lazy"> is <a href="Bounded_set" title="Bounded set">bounded</a> according to <a href="Schur's_theorem#Combinatorics" title="Schur's theorem">Schur's theorem</a>, and therefore the Frobenius number exists.

<div class="mw-heading mw-heading2"><h2 id="Frobenius_numbers_for_small_n">Frobenius numbers for small n</h2></div>

A closed-form solution exists for the coin problem only where n = 1 or 2. No closed-form solution is known for n > 2.<a href="#cite_note-mw-4">[4]</a>

If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=1}</annotation>

</semantics>

</math><img src="./d9ec7e1edc2e6d98f5aec2a39ae5f1c99d1e1425.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.656ex; height:2.176ex;" alt="{\displaystyle n=1}" loading="lazy">, then we must have <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{1}=1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{1}=1}</annotation>

</semantics>

</math><img src="./3f6489d2bc20b48a0f4acb8d102124ef02af3531.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.545ex; height:2.509ex;" alt="{\displaystyle a_{1}=1}" loading="lazy"> so that all natural numbers can be formed.

If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=2}</annotation>

</semantics>

</math><img src="./a02c8bd752d2cc859747ca1f3a508281bdbc3b34.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.656ex; height:2.176ex;" alt="{\displaystyle n=2}" loading="lazy">, the Frobenius number can be found from the formula <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(a_{1},a_{2})=a_{1}a_{2}-a_{1}-a_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(a_{1},a_{2})=a_{1}a_{2}-a_{1}-a_{2}}</annotation>

</semantics>

</math><img src="./b046009d160c97e4a60f4557190a6ff69c0822db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.443ex; height:2.843ex;" alt="{\displaystyle g(a_{1},a_{2})=a_{1}a_{2}-a_{1}-a_{2}}" loading="lazy">, which was discovered by <a href="James_Joseph_Sylvester" title="James Joseph Sylvester">James Joseph Sylvester</a> in 1882.<a href="#cite_note-5">[5]</a><a href="#cite_note-8">[nb 1]</a>

Sylvester also demonstrated for this case that there are a total of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N(a_{1},a_{2})=(a_{1}-1)(a_{2}-1)/2}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N(a_{1},a_{2})=(a_{1}-1)(a_{2}-1)/2}</annotation>

</semantics>

</math><img src="./05a3a11768d366b4864f0fe1c4dffdad2bae4484.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.091ex; height:2.843ex;" alt="{\displaystyle N(a_{1},a_{2})=(a_{1}-1)(a_{2}-1)/2}" loading="lazy"> non-representable (positive) integers.

Another form of the equation for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(a_{1},a_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(a_{1},a_{2})}</annotation>

</semantics>

</math><img src="./15d643010e23d946b0c8cca8b6e6a114e929a2e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.527ex; height:2.843ex;" alt="{\displaystyle g(a_{1},a_{2})}" loading="lazy"> is given by Skupień<a href="#cite_note-9">[8]</a> in this proposition: If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{1},a_{2}\in \mathbb {N} }">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{1},a_{2}\in \mathbb {N} }</annotation>

</semantics>

</math><img src="./e9ea6ee0c8d596d4a22485660d33c53eb40b4063.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.121ex; height:2.509ex;" alt="{\displaystyle a_{1},a_{2}\in \mathbb {N} }" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gcd(a_{1},a_{2})=1}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gcd(a_{1},a_{2})=1}</annotation>

</semantics>

</math><img src="./60ec684acffa56a61d6577f7724f2f5c95838299.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.16ex; height:2.843ex;" alt="{\displaystyle \gcd(a_{1},a_{2})=1}" loading="lazy"> then, for each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\geq (a_{1}-1)(a_{2}-1)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\geq (a_{1}-1)(a_{2}-1)}</annotation>

</semantics>

</math><img src="./c958f5e3585eecc4c931e1d92fb3e4e9b581fa33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.686ex; height:2.843ex;" alt="{\displaystyle n\geq (a_{1}-1)(a_{2}-1)}" loading="lazy">, there is exactly one pair of nonnegative integers <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho }</annotation>

</semantics>

</math><img src="./1f7d439671d1289b6a816e6af7a304be40608d64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.202ex; height:2.176ex;" alt="{\displaystyle \rho }" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma }</annotation>

</semantics>

</math><img src="./59f59b7c3e6fdb1d0365a494b81fb9a696138c36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle \sigma }" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma <a_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma <a_{1}}</annotation>

</semantics>

</math><img src="./ff79b76edf393e1ecbed11685c29a708b8230ee5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.712ex; height:2.176ex;" alt="{\displaystyle \sigma <a_{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=\rho a_{1}+\sigma a_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=\rho a_{1}+\sigma a_{2}}</annotation>

</semantics>

</math><img src="./53a7da4b4b80f12d3312ace903d06a0beb81beae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.433ex; height:2.509ex;" alt="{\displaystyle n=\rho a_{1}+\sigma a_{2}}" loading="lazy">.

The formula is proved as follows. Suppose we wish to construct the number <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\geq (a_{1}-1)(a_{2}-1)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\geq (a_{1}-1)(a_{2}-1)}</annotation>

</semantics>

</math><img src="./c958f5e3585eecc4c931e1d92fb3e4e9b581fa33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.686ex; height:2.843ex;" alt="{\displaystyle n\geq (a_{1}-1)(a_{2}-1)}" loading="lazy">. Since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gcd(a_{1},a_{2})=1}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gcd(a_{1},a_{2})=1}</annotation>

</semantics>

</math><img src="./60ec684acffa56a61d6577f7724f2f5c95838299.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.16ex; height:2.843ex;" alt="{\displaystyle \gcd(a_{1},a_{2})=1}" loading="lazy">, all of the integers <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-ja_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-ja_{2}}</annotation>

</semantics>

</math><img src="./95b1666100c4235cb9912f1ca171349129d015f2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.477ex; height:2.509ex;" alt="{\displaystyle n-ja_{2}}" loading="lazy"> for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j=0,1,\ldots ,a_{1}-1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j=0,1,\ldots ,a_{1}-1}</annotation>

</semantics>

</math><img src="./baab9034e9ebc926606f7d2f112696d347d20532.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:18.907ex; height:2.509ex;" alt="{\displaystyle j=0,1,\ldots ,a_{1}-1}" loading="lazy"> are mutually distinct modulo <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{1}}</annotation>

</semantics>

</math><img src="./bbf42ecda092975c9c69dae84e16182ba5fe2e07.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.284ex; height:2.009ex;" alt="{\displaystyle a_{1}}" loading="lazy">. Thus any integer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> must be congruent modulo <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{1}}</annotation>

</semantics>

</math><img src="./bbf42ecda092975c9c69dae84e16182ba5fe2e07.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.284ex; height:2.009ex;" alt="{\displaystyle a_{1}}" loading="lazy"> to one of these residues; in particular, taking <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m=a_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=a_{1}}</annotation>

</semantics>

</math><img src="./b6616e824c377bd6292c291c7719855c0a2d1ca6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.423ex; height:2.009ex;" alt="{\displaystyle m=a_{1}}" loading="lazy"> there is a unique value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j=\sigma \geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j=\sigma \geq 0}</annotation>

</semantics>

</math><img src="./18a5ca4aec6764159df4c81b3014468d1939b086.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:9.674ex; height:2.509ex;" alt="{\displaystyle j=\sigma \geq 0}" loading="lazy"> and a unique integer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">, such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{1}=n-\sigma a_{2}+ta_{1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{1}=n-\sigma a_{2}+ta_{1}}</annotation>

</semantics>

</math><img src="./a3b9cecffdf7281623800eefdfaaeedf7d08715e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:19.195ex; height:2.343ex;" alt="{\displaystyle a_{1}=n-\sigma a_{2}+ta_{1}}" loading="lazy">. Rearranging, we have a nonnegative integer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho =1-t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho =1-t}</annotation>

</semantics>

</math><img src="./a55c12c09677695de39e76f53711eb934857691e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.143ex; height:2.676ex;" alt="{\displaystyle \rho =1-t}" loading="lazy"> so that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=\rho a_{1}+\sigma a_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=\rho a_{1}+\sigma a_{2}}</annotation>

</semantics>

</math><img src="./53a7da4b4b80f12d3312ace903d06a0beb81beae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.433ex; height:2.509ex;" alt="{\displaystyle n=\rho a_{1}+\sigma a_{2}}" loading="lazy">. Indeed, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho \geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho \geq 0}</annotation>

</semantics>

</math><img src="./d8e1760b2df774fbfdc7e308dbee01418c4de105.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.463ex; height:2.676ex;" alt="{\displaystyle \rho \geq 0}" loading="lazy"> because <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho a_{1}=n-\sigma a_{2}\geq (a_{1}-1)(a_{2}-1)-(a_{1}-1)a_{2}=-a_{1}+1>(-1)a_{1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho a_{1}=n-\sigma a_{2}\geq (a_{1}-1)(a_{2}-1)-(a_{1}-1)a_{2}=-a_{1}+1>(-1)a_{1}}</annotation>

</semantics>

</math><img src="./41b25aaa48bf648439831a59ff0a1b9c559f5473.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:68.301ex; height:2.843ex;" alt="{\displaystyle \rho a_{1}=n-\sigma a_{2}\geq (a_{1}-1)(a_{2}-1)-(a_{1}-1)a_{2}=-a_{1}+1>(-1)a_{1}}" loading="lazy">.

To show that exactly half of the integers <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0,1,\ldots ,ab-a-b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0,1,\ldots ,ab-a-b}</annotation>

</semantics>

</math><img src="./8733d0231652e2f86ca92eb3d46514135d0141ff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:18.673ex; height:2.509ex;" alt="{\displaystyle 0,1,\ldots ,ab-a-b}" loading="lazy"> are representable as non-negative integer linear combinations, one first shows that if the integer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\in [0,ab-a-b]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\in [0,ab-a-b]}</annotation>

</semantics>

</math><img src="./ec9aa510c6202a6027db00be86e0703da8b1b6a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.677ex; height:2.843ex;" alt="{\displaystyle k\in [0,ab-a-b]}" loading="lazy"> is representable, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N-k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N-k}</annotation>

</semantics>

</math><img src="./8b2be1ed483f56ec7456f3c17c567322141ca452.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.115ex; height:2.343ex;" alt="{\displaystyle N-k}" loading="lazy"> is not representable, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=ab-a-b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=ab-a-b}</annotation>

</semantics>

</math><img src="./343c6a242d6743e6b920017728f1b0488db65a9c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:15.298ex; height:2.343ex;" alt="{\displaystyle N=ab-a-b}" loading="lazy">.

One then shows that the converse is true as well: if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> is not representable, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N-k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N-k}</annotation>

</semantics>

</math><img src="./8b2be1ed483f56ec7456f3c17c567322141ca452.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.115ex; height:2.343ex;" alt="{\displaystyle N-k}" loading="lazy"> is representable. To show this, use the fact that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gcd(a,b)=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gcd(a,b)=1}</annotation>

</semantics>

</math><img src="./350904c65b2d8869a7b182e86b29b8b63800715d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.819ex; height:2.843ex;" alt="{\displaystyle \gcd(a,b)=1}" loading="lazy">, which allows us to write <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=xa+yb}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=xa+yb}</annotation>

</semantics>

</math><img src="./4f9fc1c998d9489185e098b34ffff12667021fb5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.863ex; height:2.509ex;" alt="{\displaystyle k=xa+yb}" loading="lazy">. Reducing and re-arranging the coefficients by adding multiples of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ab}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ab}</annotation>

</semantics>

</math><img src="./49337c5cf256196e2292f7047cb5da68c24ca95d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.227ex; height:2.176ex;" alt="{\displaystyle ab}" loading="lazy"> as necessary, we can assume <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq x<b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq x<b}</annotation>

</semantics>

</math><img src="./e125d567c38ddc2ba22b14f722343653045d5371.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.687ex; height:2.343ex;" alt="{\displaystyle 0\leq x<b}" loading="lazy"> (in fact, this <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> is the unique such <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> satisfying the equation and inequalities).

Similarly we take <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u,v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u,v}</annotation>

</semantics>

</math><img src="./7e66f4b32a0181923cc1337a5634f38241e5c697.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.491ex; height:2.009ex;" alt="{\displaystyle u,v}" loading="lazy"> satisfying <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N-k=ua+vb}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N-k=ua+vb}</annotation>

</semantics>

</math><img src="./8c26bbc7540dfa0e59cc7a819012b5d7b9e546fb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:16.739ex; height:2.343ex;" alt="{\displaystyle N-k=ua+vb}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq u<b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq u<b}</annotation>

</semantics>

</math><img src="./70618e0428b8a4e938bc613028d9ebd517a8dcb5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.687ex; height:2.343ex;" alt="{\displaystyle 0\leq u<b}" loading="lazy">. Now we can add these equations to write <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=(u+x)a+(y+v)b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=(u+x)a+(y+v)b}</annotation>

</semantics>

</math><img src="./7ee44378c556047d0bae204e69ad1179a59339ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.472ex; height:2.843ex;" alt="{\displaystyle N=(u+x)a+(y+v)b}" loading="lazy"> which, using <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=ab-a-b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=ab-a-b}</annotation>

</semantics>

</math><img src="./343c6a242d6743e6b920017728f1b0488db65a9c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:15.298ex; height:2.343ex;" alt="{\displaystyle N=ab-a-b}" loading="lazy"> yields <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ab-b(1+y+v)=a(x+u+1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ab-b(1+y+v)=a(x+u+1)}</annotation>

</semantics>

</math><img src="./9dcf3d23fc8f254b750a1c7440dd23ebd21023af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:32.641ex; height:2.843ex;" alt="{\displaystyle ab-b(1+y+v)=a(x+u+1)}" loading="lazy">. The integer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x+u+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x+u+1}</annotation>

</semantics>

</math><img src="./f683a9d05681f0d46e1142a7b9d994268cd3fc72.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.503ex; height:2.343ex;" alt="{\displaystyle x+u+1}" loading="lazy"> is positive, because <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x,u\geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x,u\geq 0}</annotation>

</semantics>

</math><img src="./e3fcc8ccded004958bf4e6d4fc551fb6f0b94c04.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.954ex; height:2.509ex;" alt="{\displaystyle x,u\geq 0}" loading="lazy">. In fact, since the left-hand side of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ab-b(1+y+v)=a(x+u+1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ab-b(1+y+v)=a(x+u+1)}</annotation>

</semantics>

</math><img src="./9dcf3d23fc8f254b750a1c7440dd23ebd21023af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:32.641ex; height:2.843ex;" alt="{\displaystyle ab-b(1+y+v)=a(x+u+1)}" loading="lazy"> is divisible by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (a,b)=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (a,b)=1}</annotation>

</semantics>

</math><img src="./91827bc70e1571ba90f89a2e90883b721897fafc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.332ex; height:2.843ex;" alt="{\displaystyle (a,b)=1}" loading="lazy">, we must have that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x+u+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x+u+1}</annotation>

</semantics>

</math><img src="./f683a9d05681f0d46e1142a7b9d994268cd3fc72.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.503ex; height:2.343ex;" alt="{\displaystyle x+u+1}" loading="lazy"> is divisible by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy">. Yet <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x,u\leq b-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x,u\leq b-1}</annotation>

</semantics>

</math><img src="./daba4ed7e01962e8678d1c11b5586974f455a726.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.792ex; height:2.509ex;" alt="{\displaystyle x,u\leq b-1}" loading="lazy">, so <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x+u+1\leq 2b-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x+u+1\leq 2b-1}</annotation>

</semantics>

</math><img src="./6fc50522e6d06397dbd8fe441c8de9e869a9b6ba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:18.764ex; height:2.343ex;" alt="{\displaystyle x+u+1\leq 2b-1}" loading="lazy">, so that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x+u+1=b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x+u+1=b}</annotation>

</semantics>

</math><img src="./8ddcf0fab0b1f0cdfda6f922ffe24352828a31d6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:13.599ex; height:2.343ex;" alt="{\displaystyle x+u+1=b}" loading="lazy">. Substituting this into <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ab-b(1+y+v)=a(x+u+1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ab-b(1+y+v)=a(x+u+1)}</annotation>

</semantics>

</math><img src="./9dcf3d23fc8f254b750a1c7440dd23ebd21023af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:32.641ex; height:2.843ex;" alt="{\displaystyle ab-b(1+y+v)=a(x+u+1)}" loading="lazy"> and subtracting <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ab}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ab}</annotation>

</semantics>

</math><img src="./49337c5cf256196e2292f7047cb5da68c24ca95d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.227ex; height:2.176ex;" alt="{\displaystyle ab}" loading="lazy"> from both sides yields <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b(1+y+v)=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b(1+y+v)=0}</annotation>

</semantics>

</math><img src="./ea1d723722cf35b1d700d5111d1c48346e624e02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.194ex; height:2.843ex;" alt="{\displaystyle b(1+y+v)=0}" loading="lazy">. So <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1+y+v=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1+y+v=0}</annotation>

</semantics>

</math><img src="./e68eae28fcf9e446292ab40201946c295b1e9300.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.387ex; height:2.509ex;" alt="{\displaystyle 1+y+v=0}" loading="lazy">. This implies that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y+v=-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y+v=-1}</annotation>

</semantics>

</math><img src="./c8c8fbc1146dcb78fbd9032c19cb702f6569afdd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.193ex; height:2.509ex;" alt="{\displaystyle y+v=-1}" loading="lazy">, which means that exactly one of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> is negative. If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> is negative, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v\geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v\geq 0}</annotation>

</semantics>

</math><img src="./8b83ef9770a86a11dfb1be6808c501b16b8e9748.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.389ex; height:2.343ex;" alt="{\displaystyle v\geq 0}" loading="lazy">, which means that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N-k=ua+vb}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N-k=ua+vb}</annotation>

</semantics>

</math><img src="./8c26bbc7540dfa0e59cc7a819012b5d7b9e546fb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:16.739ex; height:2.343ex;" alt="{\displaystyle N-k=ua+vb}" loading="lazy"> is representable; the case when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> is negative entails that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> is representable.

Thus for any non-negative integer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\in [0,ab-a-b]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\in [0,ab-a-b]}</annotation>

</semantics>

</math><img src="./ec9aa510c6202a6027db00be86e0703da8b1b6a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.677ex; height:2.843ex;" alt="{\displaystyle k\in [0,ab-a-b]}" loading="lazy">, we know that exactly one of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (ab-a-b)-k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (ab-a-b)-k}</annotation>

</semantics>

</math><img src="./cfe74d6e0859b19ef37cbd2bd0c20519330a5cf5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.996ex; height:2.843ex;" alt="{\displaystyle (ab-a-b)-k}" loading="lazy"> is representable (and these are distinct, because <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ab-a-b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ab-a-b}</annotation>

</semantics>

</math><img src="./c1a8390d3f3e818d56a36070e7d69d5e0d9d33f0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.136ex; height:2.343ex;" alt="{\displaystyle ab-a-b}" loading="lazy"> must be odd as the integers <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a,b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a,b}</annotation>

</semantics>

</math><img src="./181523deba732fda302fd176275a0739121d3bc8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.261ex; height:2.509ex;" alt="{\displaystyle a,b}" loading="lazy"> are relatively prime). This shows that half of the integers in the given range are representable; since there are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (ab-a-b+1)=(a-1)(b-1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (ab-a-b+1)=(a-1)(b-1)}</annotation>

</semantics>

</math><img src="./18f653683c6fc0406ca61ef4ac6dc410855a1d17.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:32.898ex; height:2.843ex;" alt="{\displaystyle (ab-a-b+1)=(a-1)(b-1)}" loading="lazy"> integers in the range <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [0,ab-a-b]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [0,ab-a-b]}</annotation>

</semantics>

</math><img src="./776ad89a400bc9a36459fec51ad44eb16fe14498.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.626ex; height:2.843ex;" alt="{\displaystyle [0,ab-a-b]}" loading="lazy">, this gives the desired result.

Formulae<a href="#cite_note-10">[9]</a> and fast algorithms<a href="#cite_note-11">[10]</a> are known for three numbers though the calculations can be very tedious if done by hand.

Simpler lower and upper bounds for Frobenius numbers for n = 3 have also been determined. The asymptotic lower bound due to Davison

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msqrt>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(a_{1},a_{2},a_{3})\equiv g(a_{1},a_{2},a_{3})+a_{1}+a_{2}+a_{3}\geq {\sqrt {3a_{1}a_{2}a_{3}}}}</annotation>

</semantics>

</math><img src="./618644bd05ac9c64f3f9c869f31222def4815701.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:55.762ex; height:3.509ex;" alt="{\displaystyle f(a_{1},a_{2},a_{3})\equiv g(a_{1},a_{2},a_{3})+a_{1}+a_{2}+a_{3}\geq {\sqrt {3a_{1}a_{2}a_{3}}}}" loading="lazy"></dd></dl>

is relatively sharp.<a href="#cite_note-12">[11]</a> (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> here is the modified Frobenius number, which is the greatest integer not representable by positive integer linear combinations of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{1},a_{2},a_{3}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{1},a_{2},a_{3}}</annotation>

</semantics>

</math><img src="./dd8e11b0b055a7c3471e39b9742a8e7df9883e99.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.92ex; height:2.009ex;" alt="{\displaystyle a_{1},a_{2},a_{3}}" loading="lazy">.)

The asymptotic average behaviour of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> for three variables is also known as:<a href="#cite_note-13">[12]</a>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

<msqrt>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(a_{1},a_{2},a_{3})\sim {\frac {8}{\pi }}{\sqrt {a_{1}a_{2}a_{3}}},}</annotation>

</semantics>

</math><img src="./70f9cebff028280e9a439f11321422a653ef09cd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:26.709ex; height:5.176ex;" alt="{\displaystyle f(a_{1},a_{2},a_{3})\sim {\frac {8}{\pi }}{\sqrt {a_{1}a_{2}a_{3}}},}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Wilf's_conjecture">Wilf's conjecture</h2></div>

In 1978, Wilf conjectured that given coprime integers <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{1}<a_{2}<...<a_{d}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{1}<a_{2}<...<a_{d}}</annotation>

</semantics>

</math><img src="./54d851684009893484107ec7f7dce182b3444796.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.997ex; height:2.176ex;" alt="{\displaystyle a_{1}<a_{2}<...<a_{d}}" loading="lazy">, and their Frobenius number <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F}</annotation>

</semantics>

</math><img src="./545fd099af8541605f7ee55f08225526be88ce57.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.741ex; height:2.176ex;" alt="{\displaystyle F}" loading="lazy">, we have

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d\geq {\frac {F+1}{F+1-g}},}</annotation>

</semantics>

</math><img src="./777b7608690b57ea92ac721e231c0a8c1ce0caa2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:15.497ex; height:5.676ex;" alt="{\displaystyle d\geq {\frac {F+1}{F+1-g}},}" loading="lazy"></dd></dl>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"> denotes the number of all non-representable positive integers.<a href="#cite_note-14">[13]</a> In 2015, an asymptotic version of this was proven by Moscariello and Sammartano.<a href="#cite_note-15">[14]</a>

<div class="mw-heading mw-heading2"><h2 id="Frobenius_numbers_for_special_sets">Frobenius numbers for special sets</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Arithmetic_sequences">Arithmetic sequences</h3></div>

A simple formula exists for the Frobenius number of a set of integers in an <a href="Arithmetic_sequence" class="mw-redirect" title="Arithmetic sequence">arithmetic sequence</a>.<a href="#cite_note-16">[15]</a> Given integers a, d, w with gcd(a, d) = 1:

<mrow>

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(a,a+d,a+2d,\dots ,a+wd)=\left(\left\lfloor {\frac {a-2}{w}}\right\rfloor \right)a+d(a-1)}</annotation>

</semantics>

</math><img src="./98f10990400e7eb80f83d3cafbbd2ebda4433e6d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:58.1ex; height:6.176ex;" alt="{\displaystyle g(a,a+d,a+2d,\dots ,a+wd)=\left(\left\lfloor {\frac {a-2}{w}}\right\rfloor \right)a+d(a-1)}" loading="lazy"></dd></dl>

The <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=2}</annotation>

</semantics>

</math><img src="./a02c8bd752d2cc859747ca1f3a508281bdbc3b34.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.656ex; height:2.176ex;" alt="{\displaystyle n=2}" loading="lazy"> case above may be expressed as a special case of this formula.

In the event that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a>w^{2}-3w+1}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a>w^{2}-3w+1}</annotation>

</semantics>

</math><img src="./e592454b9ec982da257ef08d5d9d7ca95f6238df.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:16.716ex; height:2.843ex;" alt="{\displaystyle a>w^{2}-3w+1}" loading="lazy">, we can omit any subset of the elements <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a+2d,a+3d,...,a+(w-3)d,a+(w-2)d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a+2d,a+3d,...,a+(w-3)d,a+(w-2)d}</annotation>

</semantics>

</math><img src="./6feb4bb716c10616d4a11331ace9cec19a17575a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:45.659ex; height:2.843ex;" alt="{\displaystyle a+2d,a+3d,...,a+(w-3)d,a+(w-2)d}" loading="lazy"> from our arithmetic seq,e and the formula for the Frobenius number remains the same.<a href="#cite_note-17">[16]</a>

<div class="mw-heading mw-heading3"><h3 id="Geometric_sequences">Geometric sequences</h3></div>

There also exists a closed form solution for the Frobenius number of a set in a <a href="Geometric_sequence" class="mw-redirect" title="Geometric sequence">geometric sequence</a>.<a href="#cite_note-18">[17]</a> Given integers m, n, k with gcd(m, n) = 1:

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(m^{k},m^{k-1}n,m^{k-2}n^{2},\dots ,n^{k})=n^{k-1}(mn-m-n)+{\frac {m^{2}(n-1)(m^{k-1}-n^{k-1})}{m-n}}.}</annotation>

</semantics>

</math><img src="./9fad0c0a6117c1bc553484217ebdf32580a35965.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:81.218ex; height:6.009ex;" alt="{\displaystyle g(m^{k},m^{k-1}n,m^{k-2}n^{2},\dots ,n^{k})=n^{k-1}(mn-m-n)+{\frac {m^{2}(n-1)(m^{k-1}-n^{k-1})}{m-n}}.}" loading="lazy"></dd>

<dd>A simpler formula that also displays symmetry between the variables is as follows. Given positive integers <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a,b,k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a,b,k}</annotation>

</semantics>

</math><img src="./5656157ab00e23ee6fe3a893adbb77d4ba3af0c1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.506ex; height:2.509ex;" alt="{\displaystyle a,b,k}" loading="lazy">, with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gcd(a,b)=1,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gcd(a,b)=1,}</annotation>

</semantics>

</math><img src="./55887d25830de3d063110181cc304ba6e1925324.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.466ex; height:2.843ex;" alt="{\displaystyle \gcd(a,b)=1,}" loading="lazy"> let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{k}(a,b)=\{a^{k},a^{k-1}b,\ldots ,b^{k}\}}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{k}(a,b)=\{a^{k},a^{k-1}b,\ldots ,b^{k}\}}</annotation>

</semantics>

</math><img src="./30e735eafa8dada45bbde944493332f50765fc49.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.359ex; height:3.176ex;" alt="{\displaystyle A_{k}(a,b)=\{a^{k},a^{k-1}b,\ldots ,b^{k}\}}" loading="lazy">. Then <a href="#cite_note-19">[18]</a></dd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(A_{k}(a,b))={\sigma }_{k+1}(a,b)-{\sigma }_{k}(a,b)-(a^{k+1}+b^{k+1}),}</annotation>

</semantics>

</math><img src="./45c8531a1ec3ce4ecbdd32880b75ff5a93112543.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:50.583ex; height:3.176ex;" alt="{\displaystyle g(A_{k}(a,b))={\sigma }_{k+1}(a,b)-{\sigma }_{k}(a,b)-(a^{k+1}+b^{k+1}),}" loading="lazy"></dd>

<dd>where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\sigma }_{k}(a,b)}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\sigma }_{k}(a,b)}</annotation>

</semantics>

</math><img src="./1dff6cba0fb3181b25ad3281ece472858b528ff3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.487ex; height:2.843ex;" alt="{\displaystyle {\sigma }_{k}(a,b)}" loading="lazy"> denotes the sum of all integers in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{k}(a,b).}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{k}(a,b).}</annotation>

</semantics>

</math><img src="./df9013ee3d0cc864f12d9e3c0eb9bd7fe0b4e3f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.549ex; height:2.843ex;" alt="{\displaystyle A_{k}(a,b).}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Examples_and_applications">Examples and applications</h2></div>

<div class="mw-heading mw-heading3"><h3 id="McNugget_numbers">McNugget numbers</h3></div>

One special case of the coin problem is sometimes also referred to as the McNugget numbers. The McNuggets version of the coin problem was introduced by Henri Picciotto, who placed it as a puzzle in Games Magazine in 1987,<a href="#cite_note-20">[19]</a> and included it in his algebra textbook co-authored with Anita Wah.<a href="#cite_note-21">[20]</a> Picciotto thought of the application in the 1980s while dining with his son at McDonald's, working out the problem on a napkin. A McNugget number is the total number of <a href="McDonald's" title="McDonald's">McDonald's</a> <a href="Chicken_McNuggets" title="Chicken McNuggets">Chicken McNuggets</a> in any number of boxes. In the <a href="United_Kingdom" title="United Kingdom">United Kingdom</a>, the original boxes (prior to the introduction of the <a href="Happy_Meal" title="Happy Meal">Happy Meal</a>–sized nugget boxes) were of 6, 9, and 20 nuggets.

According to <a href="Schur's_theorem" title="Schur's theorem">Schur's theorem</a>, since 6, 9, and 20 are (setwise) <a href="Coprime_integers#Coprimality_in_sets" title="Coprime integers">relatively prime</a>, any sufficiently large integer can be expressed as a (non-negative, integer) <a href="Linear_combination" title="Linear combination">linear combination</a> of these three. Therefore, there exists a largest non–McNugget number, and all integers larger than it are McNugget numbers. Namely, every positive integer is a McNugget number, with the finite number of exceptions:

<dl><dd>1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, and 43 (sequence <a href="https://oeis.org/A065003" class="extiw external" title="oeis:A065003">A065003</a> in the <a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>).</dd></dl>

<th style="padding:0;">Total</th>

<th>5

</th></tr>

<tr>

<th>+0

</th>

<td bgcolor="#ffffff"> 2: —

</td>

<td bgcolor="#ffffff"> 5: —

</td></tr>

<tr>

<th>+6

</th>

<td bgcolor="#ffffff"> 8: —

</td>

<td bgcolor="#ffffff">11: —

</td></tr>

<tr>

<th>+12

</th>

<td bgcolor="#ffffff">14: —

</td>

<td bgcolor="#ffffff">17: —

</td></tr>

<th>+18

</th>

<td bgcolor="#ccffcc">20:0,0,1

</td>

<td bgcolor="#ffffff">23: —

</td></tr>

<tr>

<th>+24

</th>

<td bgcolor="#ccffcc">26:1,0,1

</td>

<td bgcolor="#99cc99">29:0,1,1

</td></tr>

<tr>

<th>+30

</th>

<td bgcolor="#ccffcc">32:2,0,1

</td>

<td bgcolor="#99cc99">35:1,1,1

</td></tr>

<th>+36

</th>

<td bgcolor="#ccffcc">38:3,0,1

</td>

<td bgcolor="#99cc99">41:2,1,1

</td></tr>

<tr>

<th>+42

</th>

<td bgcolor="#ccffcc">44:4,0,1

</td>

<td bgcolor="#99cc99">47:3,1,1

</td></tr>

<tr>

<th>+48

</th>

<td bgcolor="#ccffcc">50:5,0,1

</td>

<td bgcolor="#99cc99">53:4,1,1

</td></tr>

<tr>

<th>+54

</th>

<td bgcolor="#ccffcc">56:6,0,1

</td>

<td bgcolor="#99cc99">59:5,1,1

</td></tr>

<tr>

<td colspan="7">A possible set of combinations of boxes for a total of 0 to 59 nuggets. Each triplet denotes the number of boxes of 6, 9 and 20, respectively.

</td></tr></tbody></table>

Thus the largest non–McNugget number is 43.<a href="#cite_note-22">[21]</a> The fact that any integer larger than 43 is a McNugget number can be seen by considering the following <a href="Integer_partition" title="Integer partition">integer partitions</a>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 44=6+6+6+6+20}</annotation>

</semantics>

</math><img src="./2e9de8289e1c697d0247fcb614c297739637ca9d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:23.76ex; height:2.343ex;" alt="{\displaystyle 44=6+6+6+6+20}" loading="lazy"></dd>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 45=9+9+9+9+9}</annotation>

</semantics>

</math><img src="./9110bfa420c998137177c5acf47d3fa992641277.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:22.597ex; height:2.343ex;" alt="{\displaystyle 45=9+9+9+9+9}" loading="lazy"></dd>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 46=6+20+20}</annotation>

</semantics>

</math><img src="./ef3d9563a6758e4bf4c7be6df791ca7f366f4795.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:16.916ex; height:2.343ex;" alt="{\displaystyle 46=6+20+20}" loading="lazy"></dd>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 47=9+9+9+20}</annotation>

</semantics>

</math><img src="./72011839e541d94aa03ae4edc6aaddecd139996a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:19.757ex; height:2.343ex;" alt="{\displaystyle 47=9+9+9+20}" loading="lazy"></dd>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 48=6+6+9+9+9+9}</annotation>

</semantics>

</math><img src="./dcb79079c0fb9cbf14d538b87542d05c27452028.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:26.6ex; height:2.343ex;" alt="{\displaystyle 48=6+6+9+9+9+9}" loading="lazy"></dd>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 49=9+20+20}</annotation>

</semantics>

</math><img src="./2f9d19a70df122ff60750807bd98fd4cb25f8499.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:16.916ex; height:2.343ex;" alt="{\displaystyle 49=9+20+20}" loading="lazy"></dd></dl>

Any larger integer can be obtained by adding some number of 6s to the appropriate partition above. A straightforward check demonstrates that 43 McNuggets can indeed not be purchased, as:

<ol><li>boxes of 6 and 9 alone cannot form 43 as these can only create multiples of 3 (with the exception of 3 itself);</li>

<li>including a single box of 20 does not help, as the required remainder (23) is also not a multiple of 3; and</li>

<li>more than one box of 20, complemented with boxes of size 6 or larger, obviously cannot lead to a total of 43 McNuggets.</li></ol>

Since the introduction of the 4-piece Happy Meal–sized nugget boxes, the largest non–McNugget number is 11. In countries where the 9-piece size is replaced with the 10-piece size, there is no largest non–McNugget number, as any odd number cannot be made.

<div class="mw-heading mw-heading3"><h3 id="Other_examples">Other examples</h3></div>

In <a href="Rugby_union" title="Rugby union">rugby union</a>, there are four types of scores: penalty goal (3 points), drop goal (3 points), try (5 points) and converted try (7 points). By combining these, any points total is possible except 1, 2, or 4. In <a href="Rugby_sevens" title="Rugby sevens">rugby sevens</a>, although all four types of scoring are permitted, attempts at penalty goals are rare, and drop goals are almost unknown. This means that team scores almost always consist of multiples of tries (5 points) and converted tries (7 points). The following scores (in addition to 1, 2, and 4) cannot be made from multiples of 5 and 7 and so are almost never seen in sevens: 3, 6, 8, 9, 11, 13, 16, 18 and 23. By way of example, none of these scores was recorded in any game in the <a href="2014-15_Sevens_World_Series" class="mw-redirect" title="2014-15 Sevens World Series">2014-15 Sevens World Series</a>.

Similarly, in <a href="American_football" title="American football">American football</a>, the only way for a team to score exactly one point is if a <a href="Safety_(American_football_score)" class="mw-redirect" title="Safety (American football score)">safety</a> is awarded against the opposing team when they attempt to <a href="Conversion_(gridiron_football)" title="Conversion (gridiron football)">convert</a> after a touchdown (which in this case has a value of 6). As 2 points are awarded for safeties from regular play, and 3 points are awarded for <a href="Field_goal_(football)" class="mw-redirect" title="Field goal (football)">field goals</a>, all scores other than 1–0, 1–1, 2–1, 3–1, 4–1, 5–1 and 7–1 are possible.

<div class="mw-heading mw-heading3"><h3 id="Shellsort_time_complexity">Shellsort time complexity</h3></div>

The <a href="Shellsort" title="Shellsort">Shellsort</a> algorithm is a <a href="Sorting_algorithm" title="Sorting algorithm">sorting algorithm</a> whose time complexity is currently an <a href="Open_problem" title="Open problem">open problem</a>. The worst case complexity has an upper bound which can be given in terms of the Frobenius number of a given sequence of positive integers.

<div class="mw-heading mw-heading3"><h3 id="Least_live_weight_problem">Least live weight problem</h3></div>

<a href="Petri_nets" class="mw-redirect" title="Petri nets">Petri nets</a> are useful for modeling problems in <a href="Distributed_computing" title="Distributed computing">distributed computing</a>. For specific kinds of Petri nets, namely conservative weighted circuits, one would like to know what possible "states" or "markings" with a given weight are "live". The problem of determining the least live weight is equivalent to the Frobenius problem.

<div class="mw-heading mw-heading3"><h3 id="Terms_in_expanded_power_of_a_polynomial">Terms in expanded power of a polynomial</h3></div>

When a <a href="Univariate" title="Univariate">univariate</a> polynomial is raised to some power, one may treat the exponents of the polynomial as a set of integers. The expanded polynomial will contain powers of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> greater than the Frobenius number for some exponent (when GCD=1), e.g., for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (1+x^{6}+x^{7})^{n}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (1+x^{6}+x^{7})^{n}}</annotation>

</semantics>

</math><img src="./3f20c59ce87be62302746124e6742e0b159877cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.639ex; height:3.176ex;" alt="{\displaystyle (1+x^{6}+x^{7})^{n}}" loading="lazy"> the set is {6, 7} which has a Frobenius number of 29, so a term with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{29}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{29}}</annotation>

</semantics>

</math><img src="./50f8ff90d44e5faa7c5c3238a152c084761b1a32.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.206ex; height:2.676ex;" alt="{\displaystyle x^{29}}" loading="lazy"> will never appear for any value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> but some value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> will give terms having any power of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> greater than 29. When the GCD of the exponents is not 1, then powers larger than some value will only appear if they are a multiple of the GCD, e.g. for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (1+x^{9}+x^{15})^{n}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (1+x^{9}+x^{15})^{n}}</annotation>

</semantics>

</math><img src="./f9fd82f702f264b92ae41aaa5dda8313f8864dd5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.461ex; height:3.176ex;" alt="{\displaystyle (1+x^{9}+x^{15})^{n}}" loading="lazy">, powers of 24, 27,... will appear for some value(s) of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> but never values larger than 24 that are not multiples of 3 (nor the smaller values, 1-8, 10-14, 16, 17, 19-23).

<ul><li><a href="Postage_stamp_problem" title="Postage stamp problem">Postage stamp problem</a></li>

<li><a href="Change-making_problem" title="Change-making problem">Change-making problem</a></li>

<li><a href="Sylver_coinage" title="Sylver coinage">Sylver coinage</a></li>

<li><a href="Numerical_semigroup" title="Numerical semigroup">Numerical semigroup</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-8"><a href="#cite_ref-8">^</a> The original source is sometimes incorrectly cited as,<a href="#cite_note-6">[6]</a> in which the author put his theorem as a recreational problem<a href="#cite_note-7">[7]</a> (and did not explicitly state the formula for the Frobenius number).

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFJ._Ramírez_Alfonsín2005" class="citation book cs1">J. Ramírez Alfonsín (2005). The Diophantine Frobenius problem. Oxford Univ. Press.</cite>

</li>

<li id="cite_note-kannan-2"><a href="#cite_ref-kannan_2-0">^</a> <cite id="CITEREFRavi_Kannan1992" class="citation journal cs1">Ravi Kannan (1992). "Lattice translates of a polytope and the Frobenius problem". Combinatorica. 12 (2): 161–177. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01204720">10.1007/BF01204720</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:19200821">19200821</a>.</cite>

</li>

<li id="cite_note-beidhoffer-3"><a href="#cite_ref-beidhoffer_3-0">^</a> <cite id="CITEREFD._BeihofferJ._HendryA._NijenhuisS._Wagon2005" class="citation journal cs1">D. Beihoffer; J. Hendry; A. Nijenhuis; S. Wagon (2005). <a rel="nofollow" class="external text" href="http://www.combinatorics.org/Volume_12/Abstracts/v12i1r27.html">"Faster algorithms for Frobenius numbers"</a>. Electronic Journal of Combinatorics. 12: R27. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.37236%2F1924">10.37236/1924</a>.</cite>

</li>

<li id="cite_note-mw-4">^ <a href="#cite_ref-mw_4-0">a</a> <a href="#cite_ref-mw_4-1">b</a> <cite id="CITEREFWeisstein" class="citation web cs1"><a href="Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a> <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/CoinProblem.html">"Coin Problem"</a>. <a href="MathWorld" title="MathWorld">MathWorld</a>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFSylvester,_James_Joseph1882" class="citation journal cs1">Sylvester, James Joseph (1882). "On subinvariants, i.e. Semi-Invariants to Binary Quantics of an Unlimited Order". American Journal of Mathematics. 5 (1): 134. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2369536">10.2307/2369536</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2369536">2369536</a>.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFSylvester,_James_Joseph1884" class="citation journal cs1">Sylvester, James Joseph (1884). <a rel="nofollow" class="external text" href="https://archive.org/stream/mathematicalque05unkngoog#page/n150">"Question 7382"</a>. Mathematical Questions from the Educational Times. 41: 21.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFJ._Ramírez_Alfonsín2005" class="citation book cs1">J. Ramírez Alfonsín (2005). The Diophantine Frobenius problem. Oxford Univ. Press. p. xiii.</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFSkupień1993" class="citation journal cs1 cs1-prop-long-vol"><a href="Zdzis%C5%82aw_Skupie%C5%84" title="Zdzisław Skupień">Skupień, Zdzisław</a> (1993). <a rel="nofollow" class="external text" href="http://matwbn.icm.edu.pl/ksiazki/aa/aa65/aa6545.pdf">"A generalization of Sylvester's and Frobenius' problems"</a> (PDF). Acta Arithmetica. LXV.4 (4): 353–366. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4064%2Faa-65-4-353-366">10.4064/aa-65-4-353-366</a>.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFTripathi,_A.2017" class="citation journal cs1">Tripathi, A. (2017). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jnt.2016.05.027">"Formulae for the Frobenius number in three variables"</a>. Journal of Number Theory. 170: 368–389. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jnt.2016.05.027">10.1016/j.jnt.2016.05.027</a>.</cite>

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> See <a href="Numerical_semigroup" title="Numerical semigroup">numerical semigroup</a> for details of one such algorithm.

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFM._BeckS._Zacks2004" class="citation journal cs1">M. Beck; S. Zacks (2004). "Refined upper bounds for the linear Diophantine problem of Frobenius". Adv. Appl. Math. 32 (3): 454–467. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/math/0305420">math/0305420</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0196-8858%2803%2900055-1">10.1016/S0196-8858(03)00055-1</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:119174157">119174157</a>.</cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite id="CITEREFUstinov,_A.2009" class="citation journal cs1">Ustinov, A. (2009). "The solution of Arnold's problem on the weak asymptotics of Frobenius numbers with three arguments". Sbornik: Mathematics. 200 (4): 131–160. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2009SbMat.200..597U">2009SbMat.200..597U</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1070%2FSM2009v200n04ABEH004011">10.1070/SM2009v200n04ABEH004011</a>.</cite>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite id="CITEREFWilf,_H.S.1978" class="citation journal cs1">Wilf, H.S. (1978). <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2320864">"A Circle-Of-Lights Algorithm for the "Money-Changing Problem""</a>. The American Mathematical Monthly. 85 (7): 562–565. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2320864">10.2307/2320864</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2320864">2320864</a>.</cite>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <cite id="CITEREFMoscariello,_A.Sammartano,_A.2015" class="citation journal cs1">Moscariello, A.; Sammartano, A. (2015). "On a Conjecture by Wilf About the Frobenius Number". Mathematische Zeitschrift. 280 (1–2): 47–53. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1408.5331">1408.5331</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00209-015-1412-0">10.1007/s00209-015-1412-0</a>.</cite>

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <cite id="CITEREFRamirez_Alfonsin2005" class="citation book cs1">Ramirez Alfonsin, Jorge (2005). The Diophantine Frobenius Problem. Oxford University Press. pp. 59–60.</cite>

</li>

<li id="cite_note-17"><a href="#cite_ref-17">^</a> <cite id="CITEREFLeeO'neillVan_Over2019" class="citation journal cs1">Lee, S.H.; O'neill, C.; Van Over, B. (2019). "On arithmetical numerical monoids with some generators omitted". Semigroup Forum. 98 (2): 315–326. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1712.06741">1712.06741</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00233-018-9952-3">10.1007/s00233-018-9952-3</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:119143449">119143449</a>.</cite>

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> <cite id="CITEREFOng,_Darren_C.Ponomarenko,_Vadim2008" class="citation journal cs1">Ong, Darren C.; Ponomarenko, Vadim (2008). <a rel="nofollow" class="external text" href="http://www.emis.de/journals/INTEGERS/papers/i33/i33.Abstract.html">"The Frobenius Number of Geometric Sequences"</a>. INTEGERS: The Electronic Journal of Combinatorial Number Theory. 8 (1): A33. Retrieved 2010-01-04.</cite>

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> <cite id="CITEREFTripathi2008" class="citation journal cs1">Tripathi, Amitabha (2008). "On the Frobenius Problem for Geometric Sequences, Article A43". INTEGERS: The Electronic Journal of Combinatorial Number Theory. 8 (1).</cite>

</li>

<li id="cite_note-20"><a href="#cite_ref-20">^</a> <cite id="CITEREFPicciotto1987" class="citation journal cs1">Picciotto, Henri (1987). <a rel="nofollow" class="external text" href="https://archive.org/details/games-85-1987-april/page/n53/mode/2up">"Math McPuzzle"</a>. Games Magazine. 85 (April/May): 52.</cite>

</li>

<li id="cite_note-21"><a href="#cite_ref-21">^</a> <cite id="CITEREFWahPicciotto1994" class="citation book cs1">Wah, Anita; Picciotto, Henri (1994). <a rel="nofollow" class="external text" href="http://www.mathedpage.org/attc/lessons/ch.05/5.08-building-blocks.pdf">"Lesson 5.8 Building-block Numbers"</a> (PDF). Algebra: Themes, Tools, Concepts. p. 186.</cite>

</li>

<li id="cite_note-22"><a href="#cite_ref-22">^</a> <cite id="CITEREFWeisstein" class="citation web cs1"><a href="Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a> <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/McNuggetNumber.html">"McNugget Number"</a>. <a href="MathWorld" title="MathWorld">MathWorld</a>.</cite>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFTuenter2006" class="citation journal cs1">Tuenter, Hans J. H. (April 2006). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jnt.2005.06.015">"The Frobenius problem, sums of powers of integers, and recurrences for the Bernoulli numbers"</a>. Journal of Number Theory. 117 (2): 376–386. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jnt.2005.06.015">10.1016/j.jnt.2005.06.015</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2213771">2213771</a>. <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:1097.11010">1097.11010</a>.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://www.youtube.com/watch?v=vNTSugyS038">How to order 43 Chicken McNuggets – Numberphile</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-25" href="https://en.wikipedia.org/wiki/?title=Coin_problem&oldid=1302394921">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>